package com.dragon.datastructure.sort;

import java.util.Arrays;

/**
 * 插入排序
 * <p>
 * 把n的待排序的元素看成为一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含有n-1的元素，
 * 排序过程中每次从无序表中取出第一个元素，把它的排序码依次与有序表元素的排序码进行比较，将它插入到有序表中的适当位置，
 * 使之成为新的有序表。
 *
 * @author dragon
 * @since 2019/12/23
 */
public class InsertSort {

    public static void main(String[] args) {
        //插入排序耗费的时间:8360毫秒
        Integer[] array = new Integer[80];
        for (int i = 0; i < array.length; i++) {
            array[i] = (int) (Math.random() * 800_000);
        }
        long startTime = System.currentTimeMillis();
        sort(array);
        long entTime = System.currentTimeMillis();
        System.out.println("插入排序耗费的时间:" + (entTime - startTime) + "毫秒");
        System.out.println(Arrays.toString(array));
    }

    /**
     * 插入排序
     *
     * @param source 被排序的数组
     * @param <T>    数组中的元素类型
     * @throws NullPointerException 如果传入的数组为null
     */
    public static <T extends Comparable<T>> void sort(T[] source) {
        if (source == null || source.length < 2) {
            return;
        }
        T insertValue;
        int insertIndex;
        for (int i = 1; i < source.length; i++) {
            // 待插入的值
            insertValue = source[i];
            // 待插入索引位置,默认就是自己原来的位置
            insertIndex = i;
            // 如果待排序的这个元素是小于它后面的那个元素，则要插入的位置要往后移
            while (insertIndex - 1 >= 0 && insertValue.compareTo(source[insertIndex - 1]) < 0) {
                // 将后面的较大的值往前面移动
                source[insertIndex] = source[insertIndex - 1];
                insertIndex--;
            }
            // 如果待插入到的位置不是自己原来的位置，则赋值
            if (insertIndex != i) {
                source[insertIndex] = insertValue;
            }
        }
    }

}
